package DoExercise.HSP_ZCY.A016_动态规划;

/**
 * @Author: Du
 * @Date: 2021/7/23 17:48
 * <p>
 * 范围上的尝试模型
 */
public class Code11_拿牌问题
{
    public static void main(String[] args)
    {
        int[] arr = {20, 19, 120, 100};
        System.out.println(win2(arr));
    }
    
    /**
     * 逐个填对角线的数字
     *
     * @param arr
     * @return
     */
    public static int win1(int[] arr)
    {
        if (arr == null || arr.length == 0)
        {
            return 0;
        }
        int[][] f = new int[arr.length][arr.length];
        int[][] s = new int[arr.length][arr.length];
        for (int i = 0; i < arr.length; i++)
        {
            f[i][i] = arr[i];
        }
        
        for (int i = 1; i < arr.length; i++)
        {
            int L = 0, R = i;
            while (L < arr.length && R < arr.length)
            {
                f[L][R] = Math.max(arr[L] + s[L + 1][R], arr[R] + s[L][R - 1]);
                s[L][R] = Math.min(f[L + 1][R], f[L][R - 1]);
            }
        }
        return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
    }
    
    /**
     * 从下向上填对角线的数字
     *
     * @param arr
     * @return
     */
    public static int win2(int[] arr)
    {
        if (arr == null || arr.length == 0)
        {
            return 0;
        }
        int[][] f = new int[arr.length][arr.length];
        int[][] s = new int[arr.length][arr.length];
        for (int R = 0; R < arr.length; R++)
        {
            f[R][R] = arr[R];
            for (int L = R - 1; L >= 0; L--)
            {
                f[L][R] = Math.max(arr[L] + s[L + 1][R], arr[R] + s[L][R - 1]);
                s[L][R] = Math.min(f[L + 1][R], f[L][R - 1]);
            }
        }
        return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
    }
}
